A. Field of the Invention
The present invention relates generally to clipping in a graphics system and in particular to an apparatus and method for determining line clipping intersection points.
B. Description of the Related Art
In certain computer graphics systems, the portion of a line extending beyond the display area must be clipped. For example, a computer graphics system may perform line clipping to determine which pixels are to be drawn in a window in a computer screen. Line clipping thus determines which lines to draw in the display window, and which portion of a line is to draw if the line is located partially within the display window. In conventional systems, line clipping and line drawing are low-level graphics operations, but calculations involved in clipping lines are complex and time-consuming.
For example, one conventional clipping technique compares each point of a line to the four sides of a display window before drawing the line. This seemingly simple technique requires four comparisons for every point on the line. If the line is much larger than the window, this technique can be extremely time-consuming.
Several conventional line clipping techniques determine the intersection points of a line and the display window. One technique involves intersecting a line with each of the four edges of a clipping rectangle to determine the intersection points on those edges. These, too, can involve a great deal of calculations. Other conventional line clipping techniques, such as the Cohen-Sutherland line clipping algorithm, the Cyrus-Beck technique, and a method of clipping a line by solving linear equations, require extensive multiplication and division operations and are therefore computation intensive and time-consuming. For example, an integer division instruction may take as many as 40 CPU cycles, and one integer multiplication instructions may take as many as 10 cycles on an Intel PENTIUM CPU. Furthermore, some of these techniques require floating point multiplication or division, which require even more computing resources.